package com.tensai.study.基础.算法.矩阵快速幂;

import Jama.Matrix;
import lombok.Data;

/**
 * 斐波那契数列求解
 * <p>
 * https://www.cnblogs.com/zangbo/p/5622351.html
 *
 * @author Tensai
 * 2019/2/22
 */
@Data
public class Fibonacci {

    private Matrix matrix;

    private Fibonacci() {
        double[][] base = {{1, 1}, {1, 0}};
        this.matrix = new Matrix(base);
    }

    private Matrix power(int n) {
        double[][] t = {{1, 0}, {0, 1}};
        Matrix res = this.matrix;
        Matrix ans = new Matrix(t);
        while (n != 0) {
            if ((n & 1) == 1) {
                ans = res.times(ans);
            }
            res = res.times(res);
            n = n >> 1;
        }
        return ans;
    }

    public static void main(String[] args) {
        Fibonacci Fibonacci = new Fibonacci();
        double s = Fibonacci.power(1000).get(1, 0);
        System.out.println(s);
    }
}

